package greedy

import (
	"sort"
)

type Program struct {
	start int
	end   int
}

func GetArrangeNum(programs []Program) int {
	if len(programs) == 0 {return 0}
	return ArrangeProcess(programs, 0, 0)
}

func ArrangeProcess(canArrangeP []Program, done int, endTime int) int {
	if len(canArrangeP) == 0 {
		return done
	}
	maxRP := done
	for i,v := range canArrangeP {
		if v.start >= endTime {
			canAP := copyAndExcept(canArrangeP, i)
			maxRP = max(ArrangeProcess(canAP, done+1, v.end), maxRP)
		}
	}
	return maxRP
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func copyAndExcept(canArrangeP []Program, exceptIndex int) []Program {
	ans := make([]Program, len(canArrangeP)-1)
	cur := 0
	for i,v := range canArrangeP {
		if i != exceptIndex {
			ans[cur] = v
			cur++
		}
	}
	return ans
}


type myPrograms []Program
func (p myPrograms) Len() int           { return len(p) }
func (p myPrograms) Less(i, j int) bool { return p[i].end < p[j].end}
func (p myPrograms) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func  GetArrangeNum1(programs []Program) int {
	if len(programs) == 0 {return 0}
	sort.Sort(myPrograms(programs))
	var done int
	var endTime int
	for _, v := range programs {
		if v.start >= endTime {
			done++
			endTime = v.end
		}
	}
	return done
}
